#include "Insertion.c"

#ifndef SORT_QUICK
#define SORT_QUICK

#ifndef Cutoff
// 注意 Cutoff 最小为 5，否则计算 median3 时会出错
#define Cutoff 100
#endif

ElementType median3(ElementType a[], int left, int right) {
    int center = (left + right) / 2;
    if (comparator(a[left], a[center]) > 0) {
        swap(&a[left], &a[center]);
    }
    if (comparator(a[left], a[right]) > 0) {
        swap(&a[left], &a[right]);
    }
    if (comparator(a[center], a[right]) > 0) {
        swap(&a[center], &a[right]);
    }
    // 将基准元素藏在右边
    swap(&a[center], &a[right-1]);
    return a[right-1];
}

// 快速排序算法
void quick_Sort(ElementType a[], int length) {
    if (length <= 1) {
        return;
    }
    if (length < Cutoff) {
        // 小数组使用插入排序
        insertion_Sort(a, length);
        return;
    }
    // 选取基准元素
    ElementType pivot = median3(a, 0, length-1);
    // printf("pivot: %d\n", pivot);
    // printArray(a, length);
    // 将小于基准的元素放在左边，大于基准的元素放在右边
    // 原本 int left = 0, right = length - 1;
    // 因为做 median3 时，最小元素已经放在了 a[0], 最大元素放在了 a[length-1]
    // pivot 放在了 a[length-2]
    int left = 1, right = length - 2;
    while (left < right) {
        while (left < right && comparator(a[left], pivot) <= 0) {
            left++;
        }
        while (left < right && comparator(a[right], pivot) >= 0) {
            right--;
        }
        if (left < right) {
            swap(&a[left], &a[right]);
        }
    }
    // 将基准元素放在中间
    swap(&a[left], &a[length-2]);
    // printArray(a, length);
    // 递归处理左右两边
    quick_Sort(a, left);
    quick_Sort(a+left+1, length-left-1);
}

#endif
